package ClassicalSortingAlgorithm;

import java.util.Arrays;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: ClassicalSortingAlgorithm
 * @Author: song
 * @CreateTime: 2022-09-20  15:41
 * @Description: 经典二路并归；稳定性：稳定
 * 时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
 * 空间复杂度 ：O(n)
 *
 * @Version: 1.0
 */

public class mergeSort {
    public static void main(String[] args) {
        int[] nums = {3,5,1,7,4,9,8,6,12,78,42,33,25};
        int[] ints = mergeSort(nums);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }
    }
    public static int[] mergeSort(int[] nums){
        if (nums.length < 2){
            return nums;
        }
        int middle = nums.length / 2;
        int[] arr_1 = Arrays.copyOfRange(nums,0,middle);
        int[] arr_2 = Arrays.copyOfRange(nums,middle,nums.length);
        // 分治思想，递归调用；
        return merge(mergeSort(arr_1), mergeSort(arr_2));
    }
    public static int[] merge(int[] arr_1,int[] arr_2){
        int[] sorted_arr = new int[arr_1.length + arr_2.length];
        int idx = 0, idx_1 = 0, idx_2 = 0;
        while (idx_1 < arr_1.length && idx_2 < arr_2.length){
            if (arr_1[idx_1] < arr_2[idx_2]){
                sorted_arr[idx] = arr_1[idx_1];
                idx_1 += 1;
            }else {
                sorted_arr[idx] = arr_2[idx_2];
                idx_2 += 1;
            }
            idx += 1;
        }
        if (idx_1 < arr_1.length){
            while(idx_1 < arr_1.length){
                sorted_arr[idx] = arr_1[idx_1];
                idx_1 += 1;
                idx += 1;
            }
        }
        else {
            while (idx_2 < arr_2.length){
                sorted_arr[idx] = arr_2[idx_2];
                idx_2 += 1;
                idx += 1;
            }
        }
        return sorted_arr;
    }
}
